/*
 * BinarySearch.java
 *
 */
package da522A_lab4B_2011;

/**
 *
 * @author ??
 */
public class BinarySearch {

    /** Creates a new instance of BinarySearch */
    public BinarySearch() {
    }

    //implement either recBinSearch or recBinSearch2 methods
    public int recBinSearch(int[] sortedArray, int first, int upto, int key) {

        int mid = (first + upto) / 2;
        while (first <= upto) {
            if (sortedArray[mid] == key) {
                return mid;
            } else if (sortedArray[mid] < key) {
                return recBinSearch(sortedArray, mid + 1, upto, key);
            } else {
                return recBinSearch(sortedArray, first, mid - 1, key);
            }
        }
        return -1;
    }

    public boolean recBinSearch2(int[] sortedArray, int first, int upto, int key) {

        //implement this method
        return false;
    }

//This method reports the index of the found number otherwise -1        
    public int itBinSearch(int[] sortedArray, int key) {//Binary search using iteration
        int first, middle, last;
        last = sortedArray.length - 1;
        first = 0;
        // while there are still elements to search through
        while (first <= last) {
            middle = (first + last) / 2;
            // if current middle value is the search target
            if (sortedArray[middle] == key) {
                return middle;
            } // if current middle value is less than the search target
            else if (sortedArray[middle] < key) {
                first = middle + 1;
            } // if current middle value is larger than the search target
            else {
                last = middle - 1;
            }
        }
        // return -1 if search target not found
        return -1;
    }

//This method reports if the searched number is found or not
    public boolean itBinSearch2(int[] sortedArray, int key) {//Binary search using iteration
        int first, middle, last;
        last = sortedArray.length - 1;
        first = 0;
        // while there are still elements to search through
        while (first <= last) {
            middle = (first + last) / 2;
            // if current middle value is the search target
            if (sortedArray[middle] == key) {
                return true;
            } // if current middle value is less than the search target
            else if (sortedArray[middle] < key) {
                first = middle + 1;
            } // if current middle value is larger than the search target
            else {
                last = middle - 1;
            }
        }
        // return false if search target not found
        return false;
    }
}
